package main.java.data_structure;


public class MinHeap<Item extends Comparable> {
	private Item[] data;
	private int count;
	private int capacity;

	public MinHeap(int capacity) {
		this.data = (Item[])new Comparable[capacity+1];
		count = 0;
		this.capacity = capacity;
	}

	public MinHeap(Item[] arr, int n) {
		data =(Item[])new Comparable[n+1];
		capacity = n;
		for (int i = 0; i < n; i++) {
			data[i] = arr[i];
		}
		count = n;
		for (int i = count / 2; i >= 1; i--) {
			shiftDown(i);
		}
	}

	public int size() {
		return count;
	}

	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * 入队 放在最后一个位置，并跟父结点 比较直到有序
	 *
	 * @param t
	 */
	public void insert(Item t) {
		if (count == capacity) {
			Item[] data = (Item[])new Comparable[2 * capacity + 1];
			System.arraycopy(this.data, 0, data, 0, capacity + 1);
			this.data = data;
			this.capacity = 2 * capacity;
		}
		data[count + 1] = t;
		count++;
		shiftUp(count);
	}

	private void shiftUp(int k) {
		while (k > 1 && data[k/2].compareTo(data[k]) > 0) {
			this.swap(data, k, k / 2);
			k /= 2;
		}
	}

	/**
	 * 出队 把第一个元素出队，并且将最后一个元素放在第一个元素重新排序
	 *
	 * @return
	 */
	public Item extractMin() {
		assert (count > 0);

		Item ret = data[1];
		this.swap(data, 1, count);
		count--;
		shiftDown(1);
		return ret;
	}

	private void shiftDown(int k) {
		while (2 * k <= count) {
			int j = 2 * k; //在此循环中，data[k]和data[j]交换位置
			if (j + 1 <= count && data[j+1].compareTo(data[j]) < 0) {
				j += 1;
			}
			if (data[k].compareTo(data[j]) <= 0) {
				break;
			}
			this.swap(data, k, j);
			k = j;
		}
	}

	public void swap(Item[] arr, int i, int j) {
		Item temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}